1. Field of the Invention
The present invention relates generally to image processing, and in particular, to a method, apparatus, and article of manufacture for filling an area of an image.
2. Description of the Related Art
A common thing users of drawing, painting and image processing software do is fill an area of an image with a solid color, color gradient (two or more colors fading into one another), or texture. This operation is usually called “flood fill”. Another common thing users do in such software is select an area of more or less uniform color to which they want to limit the effects of subsequent actions. This is usually called “magic wand” selection. In both cases, the user clicks on a pixel in the image (referred to herein as the “anchor pixel”), and a system/methodology is needed to find “fillable” pixels: pixels similar in color to the anchor pixel, and adjacent to either the anchor pixel or to another fillable pixel. There are lots of different ways such a system and methodology can be implemented. The efficiency and complexity of the system and methodology can vary widely. Efficiency is very important, since the system and methodology needs to examine potentially millions of pixels to determine whether they are fillable. Complexity is less critical than efficiency, but still important, since a complex system and methodology is harder for a software development team to understand, maintain, and enhance than a simple one.
Prior art systems for performing flood fill operations often examine the value of each pixel in an image at least four times. In this regard, prior art solutions utilize a collection of pixels to be processed. Having determined a pixel to be fillable, the pixels above, below, to the left, and to the right of the fillable pixel are added to the collection of pixels to be processed. This means it is common for a given pixel of the image to be checked four times.
Accordingly, what is needed is a system and methodology for determining, locating, and filling pixels in an efficient and simple manner.